/*
* 算法：递归
*
* 思路：
* 先左深度遍历和先右深度遍历值相等即可
* */

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    public boolean isSymmetric(TreeNode root) {
        if(root.right==null&&root.left==null)
        {
            return true;
        }

        if(root.left==null||root.right==null)
        {
            return false;
        }

        if(leftDfs(root.left).equals(rightDfs(root.right)))
        {
            return true;
        }


        return false;
    }

    //先根，先左深度遍历
    public List<Integer> leftDfs(TreeNode node)
    {
        List<Integer> list = new ArrayList<>();
        list.add(node.val);

        if(node.left!=null)
        {
            list.addAll(leftDfs(node.left));
        }
        else {
            list.add(null);
        }
        if(node.right!=null)
        {
            list.addAll(leftDfs(node.right));
        }
        else {
            list.add(null);
        }
        return list;
    }

    //先根，先右深度遍历
    public List<Integer> rightDfs(TreeNode node)
    {
        List<Integer> list = new ArrayList<>();
        list.add(node.val);

        if(node.right!=null)
        {
            list.addAll(rightDfs(node.right));
        }
        else {
            list.add(null);
        }
        if(node.left!=null)
        {
            list.addAll(rightDfs(node.left));
        }
        else {
            list.add(null);
        }
        return list;
    }
}
